/*Project 1 - Simulate a single customer queue : M/M/1/K queue
 * Author : Saurabh V. Pendse
 * Unity ID : svpendse
 * Student ID : 001026185
*/
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stdint.h>
#include <time.h>
#define IA 16807
#define IM 2147483647
#define AM (1.0/IM)
#define IQ 127773
#define IR 2836
#define MASK 123459876
using namespace std;

//forward declaration of the structures
typedef struct Customer Customer;
typedef struct EventNode EventNode;


vector<Customer *> customer_list;	//the list of all customers (arrived + lost)
vector<EventNode *> event_list;		//the event list
queue<Customer *> customer_queue;	//the customer queue


//Customer structure
typedef struct Customer {
	uint32_t id_;					//the customer ID
	double arrival_time_;			//the arrival time
	double service_time_;			//the service time
	double waiting_time_;			//the waiting time
	double departure_time_;			//the departure time
	uint32_t customers_after_;		//the number of customers in the system immediately after this customer 
	bool lost_, serviced_;			//flags to indicate whether the customer has been served yet, or has 									 
									//been lost
	uint32_t departure_number_;
	//constructor to initialize a Customer
	Customer(uint32_t id, double arrival_time, double service_time,
			double waiting_time, double departure_time,
			bool serviced, bool lost) : id_(id), arrival_time_(arrival_time),
	service_time_(service_time), waiting_time_(waiting_time), departure_time_(departure_time),
	serviced_(serviced), lost_(lost) {
		customers_after_ = 0;
		departure_number_ = -1;
	}
	//utility function to print the customer information
	void print() {
		cout << "Id : " << id_ << ", Arrival time = " << arrival_time_
			<< ", Service time = " << service_time_
			<< ", Waiting time = " << waiting_time_
			<< ", Departure time = " << departure_time_
			<< ", Lost = " << lost_
			<< ", serviced = " << serviced_ 
			<< ", customers after = " << customers_after_ << endl;
	}
}Customer;


typedef struct EventNode {
	char type_;						//event type ('A', 'D' or 'L')
	Customer *customer_;			//pointer to the corresponding customer
	double time_;					//the time of the event
	//constructor to initialize an event
	EventNode(char type, Customer *customer, double time) : type_(type),
	customer_(customer), time_(time) {
	}
	//utility function to print the event information
	void print() {
		if (customer_ != NULL) {
			cout << "Type : " << type_ << ", id : " << customer_->id_
				<< ", time : " << time_ << ", queue size = " << customer_queue.size() << endl;
		}
	}

}EventNode;


double lambda, mu;					//parameters for the interarrival and service time exp. dist.
uint32_t k, c, l;					//k = queue capacity, c = customers to be served, l = parameter
double Ta, Ts;						//The interarrival and service times
int n;								//number of customers in the queue
double t1, t2, te;					//times to run the simulation
uint32_t arrival_count, departure_count, total_arrival_count, total_departure_count;		//counters
uint32_t serve_count;				//the number of customers served
double master_clock;				//the master clock
double sim_time;					//the simulation time

static long kSeed_arrival = time(NULL);				//seed for the generating the interarrival times
static long kSeed_service = time(NULL) + 10467;		//seed for the generating the service times


//checks whether the event list is empty
bool event_list_empty() {
	return event_list.empty();
}

//returns the current size of the event list
uint32_t event_list_size() {
	return event_list.size();
}


//returns the first element (i.e. the next event) from the event list
EventNode *event_list_front() {
	if (! event_list_empty()) {
		return event_list[0];
	}
	return NULL;	
}

//adds a new element (i.e. a new event) to the event list, ordered by the time of the event
void event_list_add(EventNode *eventNode) {
	if (event_list_empty()) {
		event_list.push_back(eventNode);
		return;
	} else if (event_list_size() == 1) {
		if (event_list[0]->time_ <= eventNode->time_) {
			event_list.push_back(eventNode);
		} else {
			event_list.insert(event_list.begin(), eventNode);
		} 
	} else {
		uint32_t count = 0;
		while (event_list[count]->time_ <= eventNode->time_) { 
			count++;
			if (count == event_list_size()) {
				break;
			}
		}
		if (count < event_list_size()) {
			event_list.insert(event_list.begin() + count, eventNode);
		} else {
			event_list.push_back(eventNode);
		}
	}
}

//removes an element (i.e. the next event) from the event list
EventNode *event_list_remove_front() {
	if (event_list_empty()) {
		return NULL;
	}
	EventNode *event = event_list_front();
	event_list.erase(event_list.begin());
	return event;
}

//prints the contents of the event list
void event_list_print() {
	cout << "\n\n\nSTART\n\n\n";
	for (uint32_t index = 0; index < event_list.size(); ++index) {
		event_list[index]->print();
	}
	cout << "\n\n\nEND\n\n\n";
}


//function to generate the random number in the range (0, 1), given a seed
double ran0(long *idnum) {
	long k;      
	double ans;

	*idnum ^= MASK;
	k = (*idnum)/IQ;
	*idnum = IA * (*idnum - k * IQ) - IR * k;
	if (*idnum < 0) {
		*idnum += IM;
	}
	ans = AM * (*idnum);
	*idnum ^= MASK;
	return ans;
}

//function to generate an exponentially distributed random number with mean 1
double expdev(long *idnum) {
	double dummy;
	do {
		dummy = ran0(idnum);
	} while (dummy == 0.0);
	return -log(dummy);
}

//function to generate an exponentially distributed random number with mean "mean"
double expntl(double mean, long &seed) {
	return 1.0 * mean * expdev(&seed);
}

//initializes the parameters for the simulation
void init(int argc, char **argv) {

	//command line inputs and validations
	lambda = atof(argv[1]);		//0 < lambda < 1
	if (lambda >= 1) {
		cout << "Invalid value of lambda. lambda must be in (0, 1)" << endl;
		return;
	}
	mu = 1;						//mu = 1 always
	k = atoi(argv[2]);
	if (k <= 0) {
		cout << "Invalid value of K. K must be greater than 0" << endl;
		return;
	}
	c = atoi(argv[3]);
	if (c <= 0) {
		cout << "Invalid value of C. C must be greater than 0" << endl;
		return;
	}
	l = atoi(argv[4]);

	if (l == 0 || l + 11 > c) {
		cout << "Invalid value of L. (L + 11) > C" << endl;
		exit(0);
	}

	Ta = 200.0;
	Ts = 100.0;
	te = 1<<30;
	n = 0;
	t1 = expntl(Ta, kSeed_arrival);
	t2 = te;
	sim_time = 0.0;	

	serve_count = 0;
	master_clock = 0;

	arrival_count = 0;
	departure_count = 0;
	total_arrival_count = 0;
	total_departure_count = 0;

	//initiate the arrival of the first customer, generate the corresponding event,
	//add it to the event list and add the customer to the customer_list
	//set simulation time
	Customer *customer = new Customer(total_arrival_count++, t1, 0.0, 0.0, 0.0, false, false);
	EventNode *next_event = new EventNode('A', customer, t1);
	event_list_add(next_event);
	sim_time = t1;
	customer_list.push_back(customer);
}

//schedule a departure event for a given customer
void schedule_departure(Customer *customer) {
	//set the service time
	Ts = expntl(1/mu, kSeed_service);
	customer->service_time_ = Ts;
	//create a departure event and add it to the event list
	EventNode *current_departure = new EventNode('D', customer, sim_time + Ts);
	event_list_add(current_departure);
}

//process an arrival event
void process_arrival(EventNode *next_event) {
	//generate the next inter-arrival time
	Ta = expntl(1/lambda, kSeed_arrival);
	//set the simulation time to the time of the next event
	sim_time = next_event->time_;
	//create a new customer for the next arrival and add it to the event list
	Customer *customer = new Customer(total_arrival_count++, sim_time + Ta, 0, 0, 0, false, false); 
	customer_list.push_back(customer);
	//if the queue is not full, add the customer to the queue, increment n.
	//if there is only one customer in the queue, schedule a departure event for this customer
	//schedule the next arrival event
	//
	//else the customer is lost and cannot be serviced
	//create a new lost event and add it to the event list
	if (n < k) {
		arrival_count++;
		customer_queue.push(next_event->customer_);
		n++;
		if (n == 1) {
			schedule_departure(next_event->customer_);
		}
		EventNode *next_arrival = new EventNode('A', customer, sim_time + Ta);
		event_list_add(next_arrival);

	} else {
		customer->lost_ = true;
		customer->serviced_ = false;
		EventNode *lost_arrival = new EventNode('L', customer, sim_time + Ta);
		event_list_add(lost_arrival);
	}
}

//process the lost event
void process_lost(EventNode *next_event) {
	//generate the next inter-arrival time
	Ta = expntl(1/lambda, kSeed_arrival);
	//set the simulation time to the time of the next event
	sim_time = next_event->time_;
	//create a new customer for the next arrival and add it to the event list
	Customer *customer = new Customer(total_arrival_count++, sim_time + Ta, 0, 0, 0, false, false); 
	customer_list.push_back(customer);
	//if the queue is not full, schedule the next event with the newly created customer
	//note that we since the customore for next_event is lost, we do not add it to the queue
	//
	//else
	//this customer is also lost and cannot be serviced
	//create a new lost event and add it to the event list
	if (n < k) {
		EventNode *next_arrival = new EventNode('A', customer, sim_time + Ta);
		event_list_add(next_arrival);

	} else {
		customer->lost_ = true;
		customer->serviced_ = false;
		EventNode *lost_arrival = new EventNode('L', customer, sim_time + Ta);
		event_list_add(lost_arrival);
	}
}

void process_departure(EventNode *next_event) {
	//if the queue is not empty, select the front customer in the queue as the departing_customer
	//set the simulation time to the time of the next_event
	//set the departure_time_, serviced_ and lost_ properties of this customer
	//remove the customer from the queue
	//set the number of customers in the queue parameter for this customer
	//decrement n
	//increment the serve_count
	//if there are still customers in the queue, schedule the next departure event
	if (! customer_queue.empty()) {
		Customer *departing_customer = next_event->customer_;
		sim_time = next_event->time_;
		departing_customer->departure_time_ = sim_time;
		departing_customer->serviced_ = true;
		departing_customer->lost_ = false;
		departing_customer->departure_number_ = ++departure_count;
		customer_queue.pop();
		departing_customer->customers_after_ = customer_queue.size();
		n--;
		serve_count++;
		if (n > 0) {
			schedule_departure(customer_queue.front());
		}
	} 
}

//function to print the customer diagnostics, given a customer index [1...C]
void customer_diagnostics(uint32_t index) {
	if (index == 0 || index > customer_list.size()) {
		cout << "simtime in arrival = " << sim_time << endl;
		cout << "Specified customer ID out of range" << endl;
		return;
	}
	cout << "Customer " << index << endl;
	if (customer_list[index - 1]->serviced_) {
		cout << "Arrival time = " << customer_list[index - 1]->arrival_time_ << endl;
		cout << "Service time = " << customer_list[index - 1]->service_time_ << endl;
		cout << "Departure time = " << customer_list[index - 1]->departure_time_ << endl;
		cout << "Number of customers in the system after the departure = " << customer_list[index - 1]->customers_after_ << endl;
	} else {
		cout << "Not serviced. Setting departure time = arrival time" << endl;
		customer_list[index - 1]->departure_time_ = customer_list[index - 1]->arrival_time_;
	}
}


int main(int argc, char **argv) {
	double start_time, end_time;
	start_time = clock();			// simulation start timer
	init(argc, argv);
	//main simulation loop
	while (serve_count < c) {
		EventNode *event = event_list_remove_front();
		if (event != NULL) {
			if (event->type_ == 'A') {
				process_arrival(event);
			} else if (event->type_ == 'D') {
				process_departure(event);
			} else if (event->type_ == 'L') {
				process_lost(event);
			}
		} else {
			Ta = expntl(1/lambda, kSeed_arrival);
			Customer *customer = new Customer(total_arrival_count++, sim_time + Ta, 0.0, 0.0, 0.0, false, false);
			EventNode *next_event = new EventNode('A', customer, sim_time + Ta);
			event_list_add(next_event);
			customer_list.push_back(customer);
		}
	}
	total_arrival_count--;
	end_time = clock();				// simulation end timer

	//statistics calculations
	double avg_service_time = 0, avg_waiting_time = 0;
	uint32_t customers_lost = 0, customers_serviced = 0;
	for (uint32_t index = 0; index < customer_list.size(); ++index) {
		customer_list[index]->waiting_time_ = customer_list[index]->departure_time_ - 
										      customer_list[index]->service_time_ -
											  customer_list[index]->arrival_time_;
		if (customer_list[index]->serviced_ & ! customer_list[index]->lost_) {
			customers_serviced++;
			avg_service_time += customer_list[index]->service_time_;
			avg_waiting_time += customer_list[index]->waiting_time_;
		} 
		if (customer_list[index]->lost_) {
			customers_lost++;
		}
	}
	avg_service_time /= arrival_count;
	avg_waiting_time /= arrival_count;

	//print statistics, if PRINT is defined
#ifdef PRINT
	cout << "Value of the input parameter lambda = " << lambda << endl;
	cout << "Value of the input parameter K = " << k << endl;
	cout << "Value of the input parameter C = " << c << endl;
	cout << "Value of the master clock at the end of the simulation = " << sim_time << endl;
	cout << "Customer loss rate = " << 1.0 * (total_arrival_count - arrival_count) / total_arrival_count << endl;
	cout << "Average service time = " << avg_service_time << endl;
	cout << "Average waiting time = " << avg_waiting_time << endl;
	customer_diagnostics(l);
	customer_diagnostics(l + 1);
	customer_diagnostics(l + 10);
	customer_diagnostics(l + 11);
#endif
	cout << "Simulation time = " << 1.0 * (end_time - start_time) / CLOCKS_PER_SEC << endl;
}
